/*
 * CCVisu is a tool for visual graph clustering
 * and general force-directed graph layout.
 * This file is part of CCVisu.
 *
 * Copyright (C) 2005-2011  Dirk Beyer
 *
 * CCVisu is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * CCVisu is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with CCVisu; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Please find the GNU Lesser General Public License in file
 * license_lgpl.txt or http://www.gnu.org/licenses/lgpl.txt
 *
 * Dirk Beyer    (firstname.lastname@uni-passau.de)
 * University of Passau, Bavaria, Germany
 */
package org.sosy_lab.ccvisu.clustering;

import java.util.ArrayList;
import java.util.List;
import java.util.logging.Level;

import org.sosy_lab.ccvisu.graph.GraphData;
import org.sosy_lab.ccvisu.graph.GraphVertex;
import org.sosy_lab.ccvisu.graph.Group;
import org.sosy_lab.ccvisu.graph.Group.GroupKind;
import org.sosy_lab.ccvisu.graph.Position;
import org.sosy_lab.common.LogManager;
import org.sosy_lab.util.Stopwatch;

/**
 * Implementation of a clustering algorithm based on
 * @see org.sosy_lab.ccvisu.clustering.ClustererMinDist
 * with some heuristics that enhance performance.
 */
public class CopyOfClustererMinDistPerc extends ClustererMinDist {

  /**
   * Put all nodes with a distance of at most n percent
   * of the diagonal of the layout in one cluster.
   * Heuristic that helps to minimize execution time of the algorithm.
   * A good value is 0.05
   */
  private final double maxDistancePercentToAutoMerge;

  /**
   * Stop creating clusters of the graph after all clusters
   * have a certain distance (percent of the diagonal of the layout). */
  private final double minClusterDistancePercent;

  /**
   * Constructor.
   *
   * @param graphData  Graph that should be clustered.
   * @param numberOfClusters   Number of partitions hat should be found at least.
   * @param maxDistancePercentToAutoMerge  @see ClustererMinDistPerc#maxDistancePercentToAutoMerge
   * @param minClusterDistancePercent @see ClustererMinDistPerc#minClusterDistancePercent
   */
  public CopyOfClustererMinDistPerc(GraphData graphData, LogManager logger,
      int numberOfClusters, double maxDistancePercentToAutoMerge,
      double minClusterDistancePercent) {

    super(graphData, logger, numberOfClusters);

    this.maxDistancePercentToAutoMerge = maxDistancePercentToAutoMerge;
    this.minClusterDistancePercent = minClusterDistancePercent;
  }

  @Override
  protected List<Group> internalCreateClustersOfLayout()
      throws InterruptedException {

    Stopwatch stopwatch = Stopwatch.createAndStart();

    List<Group> clusters = new ArrayList<Group>();
    List<GraphVertex> vertices = graphData.getVertices();

    //
    // Initially put each node in a separate cluster.
    //
    setProgress(0, vertices.size(), "Creating initial clusters.");

    double minX = Double.MAX_VALUE;
    double minY = Double.MAX_VALUE;
    double minZ = Double.MAX_VALUE;

    double maxX = Double.MIN_VALUE;
    double maxY = Double.MIN_VALUE;
    double maxZ = Double.MIN_VALUE;

    int clusterSeqNr = 0;
    for (GraphVertex vertex : vertices) {
      Group vertexCluster = new Group("Cluster " + clusterSeqNr++, graphData);
      vertexCluster.setKind(GroupKind.CLUSTER);
      vertexCluster.addNode(vertex);
      clusters.add(vertexCluster);

      Position vertexPos = vertex.getPosition();

      maxX = Math.max(maxX, vertexPos.getX());
      maxY = Math.max(maxY, vertexPos.getY());
      maxZ = Math.max(maxZ, vertexPos.getZ());

      minX = Math.min(minX, vertexPos.getX());
      minY = Math.min(minY, vertexPos.getY());
      minZ = Math.min(minZ, vertexPos.getZ());
    }

    double layoutDistanceX = Math.abs(maxX - minX);
    double layoutDistanceY = Math.abs(maxY - minY);
    double layoutDistanceZ = Math.abs(maxZ - minZ);

    double layoutDiagonal = Math.sqrt(
          layoutDistanceX * layoutDistanceX
        + layoutDistanceZ * layoutDistanceZ
        + layoutDistanceY * layoutDistanceY);

    //
    // Calculate the parameters.
    //
    int initialNumOfClusters = clusters.size();
    double maxDistanceToAutoMerge = layoutDiagonal * maxDistancePercentToAutoMerge;
    double minClusterDistanceAbsoulte = layoutDiagonal * minClusterDistancePercent;

    //
    // Aggregate cluster until there are only k clusters left.
    //
    boolean needMoreClusterMerging = true;
    while (needMoreClusterMerging) {
      int numOfClustersBeforeIteration = clusters.size();

      setProgress(initialNumOfClusters - numOfClustersBeforeIteration,
          initialNumOfClusters, "Creating clusters");
      logger.log(Level.INFO, "Num of non-empty clusters: " + numOfClustersBeforeIteration);

      // Calculate the distance between all clusters.
      // Merge clusters if their distance is less than lMaxDistanceToAutoMerge.
      double nearestPairDistance = Double.MAX_VALUE;
      int nearestPairIndexB = -1;
      int nearestPairIndexA = -1;
      ClusterPair nearestPair = null;

      for (int a = clusters.size() - 1; a >= 0; a--) {
        Group clusterA = clusters.get(a);

        if (Thread.interrupted()) {
          throw new InterruptedException();
        }

        for (int b = a - 1; b >= 0; b--) {
          Group clusterB = clusters.get(b);

          ClusterPair clusterPair = new ClusterPair(clusterA, clusterB, null, null);
          double pairDistance = clusterPair.getEucDistanceBetweenBarycenters();

          // First stage merging:
          //    Merge clusters without recalculating the distances to the
          //    merged clusters.
          // * Only merge clusters having a distance less than...
          if (pairDistance < minClusterDistanceAbsoulte) {
            // * Merge all clusters within a certain distance...
            if (pairDistance < maxDistanceToAutoMerge) {
              // Merge the pair of clusters with the smallest distance.
              mergeClusters(clusterPair.clusterA, clusterPair.clusterB);
              clusters.remove(a);
              if (a == nearestPairIndexA || b == nearestPairIndexB) {
                // Nearest pair is now invalid.
                nearestPairIndexA = -1;
                nearestPairIndexB = -1;
                nearestPair = null;
                nearestPairDistance = Double.MAX_VALUE;
              }

              if (a < nearestPairIndexA) {
                nearestPairIndexA--;
              }

              if (a < nearestPairIndexB) {
                nearestPairIndexB--;
              }
              break;
            } else {
              if (nearestPairDistance > pairDistance) {
                nearestPair = clusterPair;
                nearestPairDistance = pairDistance;
                nearestPairIndexA = a;
                nearestPairIndexB = b;
              }
            }
          }
        }
      }

      if (nearestPair != null) {
        // Merge the pair of Clusters with the shortest distance.
        if (nearestPairDistance < minClusterDistanceAbsoulte) {
          // Important: Merge to the not empty cluster!
          int sourceGroupIndex = nearestPairIndexA;
          Group sourceGroup = nearestPair.clusterA;
          Group targetGroup = nearestPair.clusterB;

          if (targetGroup.getNodes().size() == 0) {
            sourceGroupIndex = nearestPairIndexB;
            sourceGroup = nearestPair.clusterB;
            targetGroup = nearestPair.clusterA;
          }

          mergeClusters(sourceGroup, targetGroup);
          clusters.remove(sourceGroupIndex);
        }
      }

      // More merging of clusters necessary?
      needMoreClusterMerging = (clusters.size() > numberOfClusters) //<-- Still more clusters than desired.
          && (numOfClustersBeforeIteration != clusters.size()); //<-- Merge of clusters still possible.
    }

    setProgress(1, 1, stopwatch.stop().toString());

    return clusters;
  }
}
